#include <vector>
#include <algorithm>

void InsertSort(std::vector<int>& nums)
{
   int n = nums.size();
   for (int i = 1; i < n; ++i)
   {
      int curPoke = nums[i];
      int p = i - 1;
      while (p >= 0 && nums[p] > curPoke)
      {
	 std::swap(nums[p], nums[p + 1]);
	 --p;
      }
      nums[p + 1] = curPoke;
   }
}

void ShellSort(std::vector<int>& nums)
{
   int n = nums.size();
   int gap = n;
   while (gap > 1)
   {
      gap = gap / 3 + 1;
      for (int i = 0; i < n; ++i)
      {
         int end = i - gap;
         int curPoke = nums[i];
         while (end >= 0 && nums[end] > curPoke)
         {
            std::swap(nums[end], nums[end + gap]);
            end -= gap;
         }
         nums[end + gap] = curPoke;
      }
   }
}

void SelectSort(std::vector<int>& nums)
{
   int n = nums.size();
   int left = 0, right = n - 1;
   while (left < right)
   {
      int minI = left, maxI = left;
      for (int i = left; i <= right; ++i)
      {
         minI = nums[i] < nums[minI] ? i : minI;
         maxI = nums[i] > nums[maxI] ? i : maxI;
      }
      std::swap(nums[maxI], nums[right--]);
      std::swap(nums[minI], nums[left++]);
   }
}
